package com.company;

public class horse_sun {
    public static int n=5,m=4;
    public static int x=1,y=1,count;
    public static int Fx[]={1,2,2,1,-1,-2,-2,-1};
    public static int Fy[]={2,1,-1,-2,-2,-1,1,2};
    public static int a[][]=new int [n+1][m+1];
    public static void main(String []args) {
        int dep=1;
        count=0;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++) {
                a[i][j]=0;
            }
        }
        a[x][y]=1;
        Try(x,y,2);
        if(count==0)
            System.out.println("无解");
        else {
            System.out.println("count="+count);
        }
    }
    public static boolean check(int xx,int yy) {

        if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&a[xx][yy]==0) {//任一点超界
            return true;
        }
        return false;
    }

    public static void Try(int x,int y,int dep) {
        int xx,yy;
        for(int i=0;i<=7;i++) {  //马跳八方
            xx=x+Fx[i];          //马跳后的x坐标
            yy=y+Fy[i];          //马跳后的y坐标
            if(check(xx,yy)) {
                a[xx][yy]=dep;   //a[x][y]是第几次跳到的
                if(dep==n*m)
                    output();
                else {
                    Try(xx,yy,dep+1);
                }
                a[xx][yy]=0; //回溯清理
            }
        }
    }

    public static void output() {
        count++;
        System.out.println("马走的位置：");
        for(int y=1;y<=n;y++)
            for(int x=1;x<=m;x++) {
                System.out.print(a[y][x]+" ");
            }
        System.out.println();
    }
}


